# 逻辑上说，算不上 solution2，只能算 solution1 的简化版
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1

        s, e = 0, len(nums)
        while s < e:

            mid = (e-s) // 2 + s
            midv = nums[mid]
            first, last = nums[s], nums[e - 1]
            rotated = first > last # 不存在重复的元素

            if target == midv:
                return mid
            else:
                if rotated:
                    leftRotated = first > midv
                    if leftRotated:
                        if midv <= target and target <= last:
                            s = mid + 1
                        else:
                            e = mid
                    else:
                        if first <= target and target <= midv:
                            e = mid
                        else:
                            s = mid + 1
                else:
                    if target < midv:
                        e = mid
                    else:
                        s = mid + 1
        return -1